import json

ROWS = 9
COLS = 9

numQueue = []
resultStack= []

# board = []

board = [
    [9,2,1,5,4,6,7,3,8],
    [6,5,7,8,3,9,2,4,1],
    [4,3,8,0,7,0,6,5,9],
    [5,1,0,0,0,0,0,6,2],
    [7,8,9,0,5,0,4,1,3],
    [2,6,0,0,0,0,0,7,5],
    [1,4,5,0,2,0,3,8,6],
    [3,9,6,4,1,8,5,2,7],
    [8,7,2,3,6,5,1,9,4]
]

# board = [
#     [0,0,0,0,0,0,0,0,0],
#     [0,0,0,0,0,0,0,0,0],
#     [0,0,0,0,0,0,0,0,0],
#     [0,0,0,0,0,0,0,0,0],
#     [0,0,0,0,0,0,0,0,0],
#     [0,0,0,0,0,0,0,0,0],
#     [0,0,0,0,0,0,0,0,0],
#     [0,0,0,0,0,0,0,0,0],
#     [0,0,0,0,0,0,0,0,0]
# ]


def GetRowColFromIndex(idx):
    r = int(idx / ROWS)
    c = int(idx % ROWS)
    return r, c

def calc_rest_nums():
    global numQueue, board
    for i in range(ROWS):
        for j in range(COLS):
            numQueue.append(j + 1)

    for r in range(ROWS):
        for c in range(COLS):
            if board[r][c] > 0:
                numQueue.remove(board[r][c])
    numQueue.sort()

def can_put_num(r, c, num):
    global board
    arr = []
    
    for i in range(COLS):
        if i == c:
            arr.append(num)
            continue
        if board[r][i] == num:
            return False
        else:
            arr.append(board[r][i])
    
    if not 0 in arr and is_nums_ready(arr) == False:
        return False
        
    arr = []
    for i in range(ROWS):
        if i == r:
            arr.append(num)
            continue
        if board[i][c] == num:
            return False
        else:
            arr.append(board[i][c])
    
    # 如果有0存在，则return True表示可以随便填
    # 如果没有0表示已经填满，这时必须是1-9
    if not 0 in arr and is_nums_ready(arr) == False:
        return False

    gr = r // 3
    gc = c // 3
    arr = []

    for rr in range(gr * 3, (gr + 1) * 3):
        for cc in range(gc * 3, (gc + 1) * 3):
            if rr == r and cc == c:
                arr.append(num)
                continue

            if board[rr][cc] == num:
                return False
            else:
                arr.append(board[rr][cc])
    
    if not 0 in arr and is_nums_ready(arr) == False:
        return False

    return True

def is_nums_ready(dataList):
    dataList.sort()
    isReady = True

    for i in range(1,ROWS + 1):
        if i != dataList[i - 1]:
            isReady = False
            break

    # for i in range(ROWS):
    #     if i + 1 != dataList[i]:
    #         isReady = False
    #         break

    return isReady

def find_next_zero(start_index):
    global board
    for i in range(start_index + 1, ROWS * COLS):
        r, c = GetRowColFromIndex(i)
        if board[r][c] == 0:
            return i

    return -1

def GetBiggerUnusedNum(num):
    global numQueue
    while num < 9:
        num += 1

        if num in numQueue:
           return num 
    
    return -1

def PutNum(cur_index, num):
    global board, numQueue, resultStack
    r, c = GetRowColFromIndex(cur_index)
    board[r][c] = num
    resultStack.append((cur_index, num))
    numQueue.remove(num)

def main():
    global board, numQueue, resultStack
    # with open(file='./sudoku.json', mode='r', encoding='utf-8') as f:
    #     ftext = f.read()

    # jsonDict = json.loads(ftext)
    # board = jsonDict['map']

    calc_rest_nums()
    cur_index = -1
    num = min(numQueue)
    cur_index = find_next_zero(cur_index)
    while len(numQueue) > 0:
        r, c = GetRowColFromIndex(cur_index)
        needRollBack = False
        if can_put_num(r, c, num):
            PutNum(cur_index, num)
            if len(numQueue) == 0:
                break
            num = min(numQueue)
            cur_index = find_next_zero(cur_index)
        else:
            next_num = GetBiggerUnusedNum(num)
            if next_num != -1:
                num = next_num
            else:
                needRollBack = True
                
        if needRollBack == True:
            found = False
            while len(resultStack) > 0:
                item = resultStack.pop()
                rollBackIndex = item[0]
                rollbackNum = item[1]
                numQueue.append(rollbackNum)
                rr, cc = GetRowColFromIndex(rollBackIndex)
                next_num = GetBiggerUnusedNum(rollbackNum)
                board[rr][cc] = 0
                if next_num != -1 and can_put_num(r, c, next_num) == True:
                    num = next_num
                    cur_index = rollBackIndex
                    found = True
                    break

                
            
            if len(resultStack) == 0 and found == False:
                print("error!")
                break

    for i in range(ROWS):
        print(board[i])
    
    outDict = {}
    outDict["map"] = board
    with open(file='./output.json', mode='w', encoding='utf-8') as f:
        jsonStr = json.dumps(outDict)
        f.write(jsonStr)

main()